//在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只
//能放在更大的盘子上面)。移动圆盘时受到以下限制: 
//(1) 每次只能移动一个盘子; 
//(2) 盘子只能从柱子顶端滑出移到下一根柱子; 
//(3) 盘子只能叠在比它大的盘子上。 
//
// 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 
//
// 你需要原地修改栈。 
//
// 示例1: 
//
//  输入：A = [2, 1, 0], B = [], C = []
// 输出：C = [2, 1, 0]
// 
//
// 示例2: 
//
//  输入：A = [1, 0], B = [], C = []
// 输出：C = [1, 0]
// 
//
// 提示: 
//
// 
// A中盘子的数目不大于14个。 
// 
// Related Topics 递归 
// 👍 67 👎 0

package com.leetcode.editor.cn.other;

import java.util.ArrayList;
import java.util.List;

//Java：汉诺塔问题
class HanotaLcci {
    public static void main(String[] args) {
        Solution solution = new HanotaLcci().new Solution();
        List<Integer> A = List.of(2, 1, 0);
        A = new ArrayList<>(A);
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        // TO TEST
        solution.hanota(A, B, C);
        C.forEach(c -> System.out.println(c));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            movePlate(A.size(), A, B, C);
        }

        /**
         * 递归解法
         *
         * @param size      需要移动盘子的数量
         * @param start     起始柱子
         * @param auxiliary 辅助柱子
         * @param target    目标柱子
         */
        private void movePlate(int size, List<Integer> start, List<Integer> auxiliary, List<Integer> target) {
            if (size == 1) {
                target.add(start.remove(start.size() - 1));
                return;
            }
            //将n-1个盘子从第一个柱子移动到第二个柱子
            movePlate(size - 1, start, target, auxiliary);
            //将第n个盘子从第一个柱子移动到第三个柱子
            target.add(start.remove(start.size() - 1));
            //再将n-1个盘子从第二个柱子移动到第三个柱子
            movePlate(size - 1, auxiliary, start, target);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)


    private void solution1(List<Integer> A, List<Integer> B, List<Integer> C) {
        int size = A.size();
        //存放柱子顺序
        List<Integer>[] lists = new List[3];
        lists[0] = A;
        if (size % 2 == 0) {
            lists[1] = B;
            lists[2] = C;
        } else {
            lists[1] = C;
            lists[2] = B;
        }
        /**
         * 两步法
         * 1.最小的圆盘移动到下一个柱子
         *   1.1 找到最小圆盘所在柱子current 和下一根柱子next
         *   1.2 最小圆盘移动到下一根柱子上
         * 2.另外两根柱子上可以移动的圆盘移动到新的柱子上，当两根柱子都非空时，移动较小的圆盘
         *   2.1找到另外两根柱子，current和pre
         *   2.2获取栈顶元素进行比较,较小的盘子移动到较大的一个柱子上
         */
        int currentIndex = 0;
        while (size > C.size()) {
            //1.1
            List<Integer> current = lists[currentIndex];
            List<Integer> next = lists[(currentIndex + 1) % 3];
            //1.2
            next.add(current.remove(current.size() - 1));
            currentIndex = (currentIndex + 1) % 3;
            //2.1
            List<Integer> pre = lists[(currentIndex + 1) % 3];
            //2.2
            //pre最小的盘子
            int plateTomovePre = pre.size() == 0 ? Integer.MAX_VALUE : pre.get(pre.size() - 1);
            //current最小的盘子
            int plateTomoveCurrent = current.size() == 0 ? Integer.MAX_VALUE : current.get(current.size() - 1);
            if (plateTomovePre > plateTomoveCurrent) {
                pre.add(current.remove(current.size() - 1));
            } else if (plateTomovePre < plateTomoveCurrent) {
                current.add(pre.remove(pre.size() - 1));
            }
        }
    }
}